package Leetcode;
import java.util.*;

/* 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

 * 有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


public class Leetcode20 {
	public static void main(String [] args) {
	 
	}
}

//善于运用栈先进后出的特点。 运用好增强的for语句 以及运用好push和pop方法
class Solution {
    public boolean isValid(String s) {
    	Stack <Character> a1 = new Stack<Character> ();
    	char [] a2 = s.toCharArray();	//将字符串转为字符数组
    	for(int i=0;i<s.length();i++) {		//遍历字符数组，若遍历到左半边括号，就将相应的右半边括号压入栈中
    		if(a2[i]=='(') a1.push(')');
    		else if(a2[i]=='[') a1.push(']');
    		else if(a2[i]=='{') a1.push('}');
    		else if(a1.isEmpty()||a1.pop()!=a2[i]) {	//若没有遍历到左半边括号，则将栈中括号弹出，看是否与字符数组中的括号对应
    			return false;		//若栈中没有括号或者栈中括号与其不对应则直接返回false
    		}
    	}return a1.isEmpty();	//若字符数组中无括号但栈中还有括号则返回false
    }
 }


